package leetcode.templates.unions;

public class UnionFindXY {

	int[] roots;
	int[] sizes;
	int[] stack;
	int size, m, n;
	//
//	boolean[] isWay;
//	boolean[] next;
//	char[][] cs;

	public UnionFindXY(int m, int n) {
		size = m * n;
		this.m = m;
		this.n = n;
		roots = new int[size];
		sizes = new int[size];
		for (int i = 0; i < size; i++) {
			roots[i] = i;
			sizes[i] = 1;
		}
		stack = new int[size];
	}

	public int findRoot(int id) {
		int root = 0, p = 0;
		while ((root = roots[id]) != id) {
			stack[p++] = id;
			id = root;
		}
		while (p > 0) {
			roots[stack[--p]] = root;
		}
		return root;
	}

	public boolean isSameSet(int id1, int id2) {
		return findRoot(id1) == findRoot(id2);
	}

	public void union(int id1, int id2) {
		int p1 = this.findRoot(id1);
		int p2 = this.findRoot(id2);
		if (p1 != p2) {
			int size1 = this.sizes[p1];
			int size2 = this.sizes[p2];
			if (size1 < size2) {
				this.roots[p1] = p2;
				this.sizes[p2] = size1 + size2;
				this.sizes[p1] = 0;
//				this.next[p2] = this.next[p1] || this.next[p2];
			} else {
				this.roots[p2] = p1;
				this.sizes[p1] = size1 + size2;
				this.sizes[p2] = 0;
//				this.next[p1] = this.next[p1] || this.next[p2];
			}
		}
	}

	public boolean isSameSet(int x1, int y1, int x2, int y2) {
		int id1 = this.index(x1, y1);
		int id2 = this.index(x2, y2);
		return this.isSameSet(id1, id2);
	}
	
	public void union2(int i, int j) {
		this.union(i - 1, j, i, j);
		this.union(i, j - 1, i, j);
	}
	
	public void union(int x1, int y1, int x2, int y2) {
		if (x1 < 0 || y1 < 0) {
			return;
		}
		int id1 = this.index(x1, y1);
		int id2 = this.index(x2, y2);
//		if (cs[x1][y1] == cs[x2][y2] && cs[x1][y1] != '0') {
			this.union(id1, id2);
//		}
//		if (cs[x1][y1] == '0') {
//			this.next[id2] = true;
//			this.next[this.findRoot(id2)] = true;
//		}
//		if (cs[x2][y2] == '0') {
//			this.next[id1] = true;
//			this.next[this.findRoot(id1)] = true;
//		}
	}

	public int index(int i, int j) {
		return i * n + j;
	}

	/// 业务逻辑

//	public void init(String[] grid) {
//		cs = new char[m][n];
//		for (int i = 0; i < m; i++) {
//			cs[i] = grid[i].toCharArray();
//		}
//		this.isWay = new boolean[size];
//		this.next = new boolean[size];
//		for (int i = 0; i < m; i++) {
//			for (int j = 0; j < n; j++) {
//				char c = cs[i][j];
//				int index = this.index(i, j);
//				if (c == '0') {
//					this.isWay[index] = true;
//					this.next[index] = true;
//					this.sizes[index] = 0;
//				} else {
//					if (this.next(i, j, cs)) {
//						this.next[index] = true;
//					}
//				}
//			}
//		}
//	}
	
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	private boolean next(int x, int y, char[][] cs) {
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
				if (cs[nextx][nexty] == '0') {
					return true;
				}
			} else {
				return true;
			}
		}
		return false;
	}


//	public int ans() {
//		int ans = 0;
//		for (int i = 0; i < size; i++) {
//			if (this.sizes[i] > 0 && !this.next[i]) {
//				ans = Math.max(ans, this.sizes[i]);
//			}
//		}
//		return ans;
//	}

}
